home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 14523 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.4 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Set-merging algorithm?
  5. Date: 15 Apr 1996 08:00:18 -0700
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Distribution: inet
  8. Message-ID: <4ktoa2INNp6s@keats.ugrad.cs.ubc.ca>
  9. References: <m1a91fx7jh9.fsf@gamma.hut.fi>
  10. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  11.  
  12. In article <m1a91fx7jh9.fsf@gamma.hut.fi>,
  13. Petri Hakola <Petri.Hakola@hut.fi> wrote:
  14. >
  15. >            'allo,
  16. >
  17. >    Is there any sophisticated algorithm for merging and building
  18. >    combinations from sets.
  19. >
  20. >    Like this:
  21. >    I have {a, b, c} + {d e} + {f} and I need to form all possible
  22. >    combinations. The amount of combs. is (of course) 3*2*1 = 6,
  23. >    and the groups are as follows:
  24. >
  25. >    {a d f} + {a e f} + {b d f} + {b e f} + {c d f} + {c e f}
  26. >
  27. >    (i.e. only one member per set is 'allowed' in one group
  28. >    (superset?))
  29.  
  30. This is called a Cartesian product (well, not quite). Your notation is
  31. different. A Cartesian product is a binary operation that forms all possible
  32. ordered pairs from the elements of two sets:
  33.  
  34.     ( {a, b, c}  X  { d, e } )  X  { f }
  35.  
  36. =    { <a,d>, <a,e>, <b,d>, <b, e>, <c, d>, <c, e> } X { f }
  37.  
  38. =    { <<a,d>,f>, <<a,e>,f>, <<b,d>,f>, <<b,e>,f>, <<c,d>,f>, <<c,e>,f> } 
  39.  
  40.  
  41. The difference is that the results are nested, ordered tuples.
  42.  
  43. >    If there are more than a couple of sets, the amount of time
  44. >    required to build all combinations is quite long, so I'd like
  45. >    to know is there a better way to build these than
  46. >    BruteForce. 
  47.  
  48. I can't think of a way. The fact is that if you want to actually construct the
  49. product, you have to go through all the combinations, because you have to add
  50. that many elements to the resulting set!
  51.  
  52. An alternative would be to represent the sets as trees. In other words, don't
  53. perform the combination at all, but represent them as a compound expression
  54. that you dynamically evaluate (when testing for set membership), and update
  55. (when inserting new items).
  56.  
  57.  
  58. For instance, if I know that set S is the combination of A and B (a Cartesian
  59. product, for the sake of simplicity), <x,y> is in S if and only if x is in A,
  60. and y is in B. This check is faster than searching through the entire
  61. space looking for <x,y>. Such a search is only needed when the search space
  62. does not trivially correspond to all possible combinations. In such a case,
  63. some sort of sparse matrix representation would be used anyway.
  64.  
  65. -- 
  66. I'm not really a jerk, but I play one on Usenet.
  67.